#ifndef _BUILD_REG_TREE
#define _BULID_REG_TREE

// implement build regular tree

namespace reg_tree_loc {
	enum { P_S_E_S=1, P_E_S, P_E, P_S_E, S_R_E, S_E, S_BEGIN, E_S, E_DOT, E_SET, E_RSET, E_E, E_ID, 
				E_KLEEN, E_ONE_MORE, E_ZERO_ONE,E_TIMES, E_CONCATE, E_OR, E_NOR_CHAR, S_E_END, Su_E, S_END };
	enum { PATTERN, START_CON, ENTITY, SUFFIX };			// reduction variabel
}

#include "Reg_token.h"
#include "Buf_token.h"
#include "Dfa_parse_tab.h"
#include "Build_dfa_tree.h"
#include <stack>
#include "Algorithm.h"
#include "Build_dfa_tree_loc.h"
dfa_base_str::Dfa_tree &automata::build_dfa_tree(mylib::Buffer &in, dlex::Reg_def &def, std::ostream &err) {
	using namespace dfa_base_str;
	using namespace std;
	int err_num=0;			// 0 label ok
	Reg_tree *start_tree=0, *entity=0, *suffix=0;
	Dfa_tree *tree=0;
	stack<Lex_oper*> opers;	// operations
	stack<string> back_id;		// copy some useful tokens
	stack<mylib::Set<char> > back_set;		// back up the set
	stack<int> back_int;		// back up integer
	stack<size_t> states;
	mylib::Set<char> char_set;					// for dfa's character set
	char nor_char;
	bool entity_empty=true;			// true : entity is empty, otherwise not
	bool start_line = false;		// start line build
	try {
		mylib::Buf_token<dfa_lex::Token, dfa_lex::Reg_token> token(in);
		dfa_lex::Reg_token token_id = token.get();
		states.push(0);
		for( ; ; ) {
			if( token_id == dfa_lex::UNDEF ) {
				err << "Undefined character: " << token.token() << '\n';
				throw Err_reg();
			}
			size_t cur_state = states.top();
			int action = dfa_parse_tab::actions[cur_state][token_id];		// get action
			if( action == dfa_parse_tab::ACC ) {
				tree = new Dfa_tree;
				tree->start = start_tree;
				tree->entity = entity;
				tree->suffix = suffix;
				tree->start_line = start_line;
				return *tree;
			} else if( action == dfa_parse_tab::ERR ) {	// error
				err << "Some error in your regular expression at \'" << token.token() << "\'\n";
				throw Err_reg();
			} else if ( action >= 0 ) {	// shift
				switch(token_id) {
				case dfa_lex::STR :	{	// get a string and build a dfa for it, entity : str
					const std::string &str = token.token();		// get the input string
					if( str.empty() ) {			// empty string			// build a DFA for this string
						dfa_base_str::Eplilon *ep = new dfa_base_str::Eplilon;	// build a new eplilon
						opers.push(ep);
					} else {
						dfa_base_str::Lex_oper *left=0, *right=0;
						for(size_t i=0; i < str.length(); i++ ) {
							char c = str[i];
							char_set += c;
							right = new dfa_base_str::Reg_base(c);
							if( left ) {
								left = new dfa_base_str::Concate(*left, *right);
							} else
								left = right;			// the first time
						}
						opers.push(left);				// push the tree
						entity_empty = false;
					}
					states.push(action);		// push the lastest state
					break;		}
				case dfa_lex::LEFT_BRACE : {	// to determine whether it [set] or [^set]
					token_id = token.get();		// get the next token
					std::string str;
					mylib::Set<char> s;
					if( token_id == dfa_lex::REV ) {	// [^set]
						token.push((*const_cast<string *> (&token.token())), dfa_lex::REV);	// push '^' back
					} else  {		// [set]
						in.ret(token.token().size());				// push back after '['
					}
					if( build_dfa_tree_loc::get_set(in, s) ) {	//	get set, 1 label error
						err << "get set error\n";
						throw Err_reg();
					}
					back_set.push(s);				// save the set
					token.push(str, dfa_lex::SET);
					states.push(action);
					break;	}
				case dfa_lex::ID :		// save the identifier
					back_id.push((*const_cast<string *>(&token.token())));
					states.push(action);
					break;
				case dfa_lex::INT :	// save the integer
					back_int.push(atoi(token.token().c_str()));
					states.push(action);
					break;
				case dfa_lex::SUFFIX : case dfa_lex::END_LINE :				// entity suffix
					if( entity_empty ) {		// ??
						err << "Error: entity cannot be empty.\n";
						throw Err_reg();
					}
					else if( !entity ) {				// the first time
						entity = new dfa_base_str::Reg_tree;
						entity->char_set = char_set;
						entity->tree = opers.top();
						opers.pop();
						entity_empty = true;		// clear it for suffix match
						char_set.clear();
					}
					states.push(action);
					break;
				case dfa_lex::NOR_CHAR:
					nor_char = token.token()[0];			// get the normal character
					states.push(action);
					break;
				default :		// normal shift
					states.push(action);
					break;
				}
				token_id = token.get();			// get next token
			} else if ( action < 0 ) {	// reductioin
				int red_prod = -action;
				int red_var;
				int del_state_num = 0;
				switch(red_prod) {
				case reg_tree_loc::P_S_E_S :	//pattern : start_con entity suffix
					red_var = reg_tree_loc::PATTERN;
					del_state_num = 3;
					break;
				case reg_tree_loc::P_S_E :	//pattern :start_con entity
					if( entity_empty ) {		// ??				
						err << "Error: entity cannot be empty.\n";
						throw Err_reg();
					}
					entity = new Reg_tree;
					entity->tree = opers.top();				// get entity
					opers.pop();
					entity->char_set = char_set;
					char_set.clear();
					red_var = reg_tree_loc::PATTERN;
					del_state_num = 2;
					break;
				case reg_tree_loc::P_E_S :			// pattern : entity suffix
					red_var = reg_tree_loc::PATTERN;
					del_state_num = 2;
					break;
				case reg_tree_loc::P_E :				// pattern : entity
					if( entity_empty ) {		// ??
						err << "Error: entity cannot be empty.\n";
						throw Err_reg();
					}
					entity = new Reg_tree;
					entity->tree = opers.top();
					opers.pop();
					entity->char_set = char_set;
					char_set.clear();
					red_var = reg_tree_loc::PATTERN;
					del_state_num = 1;
					break;
				case reg_tree_loc::E_S :				// entity : str
					red_var = reg_tree_loc::ENTITY;
					del_state_num = 1;
					break;
				case reg_tree_loc::E_E:					// entity : ( entity )
					red_var = reg_tree_loc::ENTITY;
					del_state_num = 3;
					break;
				case reg_tree_loc::S_E :	case reg_tree_loc::S_R_E :// start_con : < entity > || start_con : < ^ entity >
					red_var = reg_tree_loc::START_CON;
					if( !entity_empty )	{	// can build	// zero label can be builded
						dfa_base_str::Lex_oper *s = opers.top();
						opers.pop();
						dfa_base_str::Start *start_con = new dfa_base_str::Start(*s);
						start_tree = new Reg_tree;
						start_tree->tree = start_con;
						start_tree->char_set = char_set;
					} else if( entity_empty ) {	// <>
						err << "Error: pattern cannot be empty.\n";		// ??
						throw Err_reg();
					}
					if( red_prod == reg_tree_loc::S_E ) {
						del_state_num = 3;
						start_line = false;			// don't exist '^'
					} else 	{						// S_R_E 
						del_state_num = 4;
						start_line = true;
					}
					entity_empty = true;			// clear it for entity match
					char_set.clear();
					break;
				case reg_tree_loc::S_BEGIN :		// start_con : ^
					red_var = reg_tree_loc::START_CON;
					start_line = true;		// to label start line exist
					entity_empty = true;
					char_set.clear();
					del_state_num = 1;
					break;
				case reg_tree_loc::E_DOT :		{				// entity : .
					red_var = reg_tree_loc::ENTITY;
					mylib::Set<char> s;
					for(int c=0; c <= SCHAR_MAX; c++ )
						if( c != '\n' )
							s.insert((char)c);
					dfa_base_str::Reg_base *base = new dfa_base_str::Reg_base(s);	// build a non-eplilon base
					opers.push(base);
					char_set += s;							// add new set into char set
					entity_empty = false;			// entity is not empty now
					del_state_num = 1;
					break;		}
				case reg_tree_loc::E_SET :	case reg_tree_loc::E_RSET : {	// entity : [ set ] || entity : [ ^ set ]
					red_var = reg_tree_loc::ENTITY;
					mylib::Set<char> s = back_set.top();
					back_set.pop();
					if( red_prod == reg_tree_loc::E_RSET ) {
						build_dfa_tree_loc::rev_set(s);
						del_state_num = 4;
					} else
						del_state_num = 3;
					dfa_base_str::Lex_oper *base=0;
					if( s.size() ) {
						entity_empty=false;
						base = new dfa_base_str::Reg_base(s);
					} else {					// build eplilon
						base = new dfa_base_str::Eplilon();
					}
					opers.push(base);
					char_set += s;
					break;					}
				case reg_tree_loc::E_ID:	{		// entity : { id }, be aware id cannot have start_con
					red_var = reg_tree_loc::ENTITY;
					std::string &id = back_id.top();
					dlex::Reg_def::const_iterator I;
					if( (I=def.find(id)) == def.end() )	{	// not exist
						err << "undefined identifier: " << id << endl;
						throw Err_reg();
					} else {		//copy it
						dfa_base_str::Lex_oper *temp = dfa_base_str::copyn_reg_tree(*I->second->tree, 1);
						if( !temp ) {				// ??
							err << "undefined error at times operation\n";
							throw Err_reg();
						} else {
							opers.push(temp);
							entity_empty=false;		//
							char_set += I->second->char_set;
						}
					}
					back_id.pop();
					del_state_num = 3;
					break;					}
				case reg_tree_loc::E_KLEEN:	{					// entity : entity *
					red_var = reg_tree_loc::ENTITY;
					dfa_base_str::Lex_oper *reg = opers.top();
					opers.pop();
					dfa_base_str::Kleen *kleen = new dfa_base_str::Kleen(*reg);
					opers.push(kleen);
					del_state_num = 2;
					break;					}
				case reg_tree_loc::E_ONE_MORE : {				// entity : entity +
					red_var = reg_tree_loc::ENTITY;
					dfa_base_str::Lex_oper *reg = opers.top();
					opers.pop();
					dfa_base_str::One_more *one_more = new dfa_base_str::One_more(*reg);
					opers.push(one_more);
					del_state_num = 2;
					break;					}
				case reg_tree_loc::E_ZERO_ONE:	{				// entity : entity ?
					red_var = reg_tree_loc::ENTITY;
					dfa_base_str::Lex_oper *reg = opers.top();
					opers.pop();
					dfa_base_str::Zero_one *zero_one = new dfa_base_str::Zero_one(*reg);
					opers.push(zero_one);
					del_state_num = 2;
					break;					}
				case reg_tree_loc::E_TIMES :	{					// entity : entity {m, n}
					red_var = reg_tree_loc::ENTITY;
					int n = back_int.top();
					back_int.pop();
					int m = back_int.top();
					back_int.pop();
					bool zero_copyed = false;
					if( m < 0 || n < 0 || m > n || (m==0 && n==0) )		{	/// error
						err << "Error: In times operator the integer value is invalid.\n";
						throw Err_reg();
					} else {
						if( entity_empty )	{			// ???
							err << "Error:there is no sense for " << m << " to " << n << " times of eplilon\n";
							throw Err_reg();
						}
						dfa_base_str::Lex_oper *reg = opers.top();
						if( m == 0 || m == 1 )		// need not copy
							;
						else {
							opers.pop();			// delete the base one from the buffer
							dfa_base_str::Lex_oper *temp = dfa_base_str::copyn_reg_tree(*reg, m-1);	// copy n times
							if( !temp ) {				// ??
								err << "undefined error at times operation\n";
								throw Err_reg();
							} else {
								dfa_base_str::Concate *con = new dfa_base_str::Concate(*reg, *temp);
								opers.push(con);
							}
						}
						int diff;
						if( (diff = n-m ) > 0 ) {
							dfa_base_str::Zero_one *z = new dfa_base_str::Zero_one(*reg);
							dfa_base_str::Lex_oper *temp = dfa_base_str::copyn_reg_tree(*z, diff);//copy different times
							opers.push(temp);
							delete z;
							zero_copyed = true;		// copyed n part
						}
						if( zero_copyed ) {			// concate m and n part
							dfa_base_str::Lex_oper *right = opers.top();
							opers.pop();
							dfa_base_str::Lex_oper *left = opers.top();
							opers.pop();
							dfa_base_str::Concate *concate = new dfa_base_str::Concate(*left, *right);
							opers.push(concate);
						}
					}
					del_state_num = 6;
					break;					}
				case reg_tree_loc::E_CONCATE:	{	// entity : entity entity
					red_var = reg_tree_loc::ENTITY;
					if( entity_empty )	{			// ???
						err << "Error:there is no sense for " << "concatenate two eplilon.\n";
						throw Err_reg();
					}
					dfa_base_str::Lex_oper *right = opers.top();
					opers.pop();
					dfa_base_str::Lex_oper *left = opers.top();
					opers.pop();
					dfa_base_str::Concate *concate = new dfa_base_str::Concate(*left, *right);
					opers.push(concate);
					del_state_num = 2;
					break;						}
				case reg_tree_loc::E_OR:		{		// entity : entity | entity
					red_var = reg_tree_loc::ENTITY;
					if( entity_empty )		{			// ???
						err << "Error:there is no sense for " << "union two eplilons.\n";
						throw Err_reg();
					}
					dfa_base_str::Lex_oper *right = opers.top();
					opers.pop();
					dfa_base_str::Lex_oper *left = opers.top();
					opers.pop();
					dfa_base_str::Union *u= new dfa_base_str::Union(*left, *right);
					opers.push(u);
					del_state_num = 3;
					break;						}
				case reg_tree_loc::E_NOR_CHAR:	{	// entity : nor_char
					red_var = reg_tree_loc::ENTITY;
					dfa_base_str::Reg_base *base = new dfa_base_str::Reg_base(nor_char);	// build regular base for char
					opers.push(base);
					entity_empty = false;
					char_set += nor_char;
					del_state_num = 1;
					break;						}
				case reg_tree_loc::Su_E:	case reg_tree_loc::S_E_END :{		// suffix : / entity | suffix : / entity $
					red_var = reg_tree_loc::SUFFIX;
					if( red_prod == reg_tree_loc::S_E_END ) {
						dfa_base_str::Reg_base *base = new dfa_base_str::Reg_base('\n');
						dfa_base_str::Lex_oper *left = opers.top();			// get entity
						opers.pop();
						dfa_base_str::Concate *concate = new dfa_base_str::Concate(*left, *base);
						opers.push(concate);
						char_set += '\n';								// add '\n'
						entity_empty = false;
						del_state_num = 3;
					} else
						del_state_num = 2;
					if( entity_empty )	{		// ???
						err << "Error: suffix cannot add a empty entity.\n";
						throw Err_reg();
					}
					suffix = new dfa_base_str::Reg_tree;
					suffix->char_set = char_set;
					suffix->tree = opers.top();
					opers.pop();
					char_set.clear();
					entity_empty = true;			// clear for matching entity
					break;					}
				case reg_tree_loc::S_END:	{	// suffix : $
					red_var = reg_tree_loc::SUFFIX;
					dfa_base_str::Reg_base *base = new dfa_base_str::Reg_base('\n');
					char_set += '\n';
					suffix = new dfa_base_str::Reg_tree;
					suffix->char_set = char_set;
					suffix->tree = base;
					char_set.clear();
					entity_empty = true;
					del_state_num = 1;
					break;					}
				default :
					err << "undefined production.\n";
					throw Err_reg();
					break;
				}
				while( del_state_num-- > 0 )		// delete the states
					states.pop();
				states.push(dfa_parse_tab::gotos[states.top()][red_var]);
				del_state_num = 0;		
			}
		}
	} catch(Err_reg) {
		err_num=1;
	} catch(std::bad_alloc) {
		err_num = 2;
	} catch(...) {
		err_num = 3;
	}
	if( err_num ) {
		while( !opers.empty() ) {
				dfa_base_str::Lex_oper *reg = opers.top();
				opers.pop();
				del_reg_tree(*reg);		// delete the regular tree
		}
		if( start_tree ) {
			del_reg_tree(*start_tree->tree);
			delete start_tree;
		}
		if( entity ) {
			del_reg_tree(*entity->tree);
			delete entity;
		}
		if( suffix ) {
			del_reg_tree(*suffix->tree);
			delete suffix;
		}
		if( tree )
			delete tree;
	}
	if(err_num==1)
		throw Err_reg();
	else if( err_num == 2 )
		throw Out_of_mem();
	else if( err_num == 3 )
		throw Undef_err();
	else
		return *tree;
}
#endif
